package NC28_最小覆盖子串;

public class Solution {
    /**
     *
     * @param S string字符串
     * @param T string字符串
     * @return string字符串
     */
    public String minWindow (String S, String T) {
        // write code here
        int[] map = new int[128];
        // 记录 T 中每个元素出现的次数
        for (int i = 0; i < T.length(); i++){
            map[T.charAt(i)]++;
        }

        // begin end 两个指针指向窗口的首位，d 记录窗口的长度， counter 记录 T 中还有几个字符没被窗口包含
        int begin = 0, end = 0, d = Integer.MAX_VALUE, counter = T.length(), head = 0;
        // end 指针一直向后遍历
        while (end < S.length()){
            // map[] > 0 说明该字符在 T 中出现，counter-- 表示对应的字符被包含在窗口，
            // 如果 S 中的字符没有在 T 中出现，则 map[] 中对应的字符 -1 后变为负值
            if (map[S.charAt(end++)]-- > 0){
                counter--;
            }
            // 当 counter == 0 时，说明窗口已经包含了 T 中的所有元素
            while (counter == 0){
                if (end - begin < d){
                    d = end - (head = begin);
                }
                if (map[S.charAt(begin++)]++ == 0){
                    // begin 开始后移，继续向后寻找。
                    // 如果 begin 后移后指向的字符在 map 中 == 0，表示是在 T 中出现的，如果没有出现，map[] 中的值会是负值
                    counter++;  // 在 T 中的某个字符从窗口中移除，所以counter++
                }
            }
        }
        return d == Integer.MAX_VALUE ? "" : S.substring(head, head + d);

    }
}